package graph

func numIslands(grid [][]byte) int {
	n, m := len(grid), len(grid[0])
	vis := make([][]bool, n)
	for i := range vis {
		vis[i] = make([]bool, m)
	}
	var dfs func (x, y int)
	dfs = func (x, y int) {
		if x < 0 || x >= n || y < 0 || y >= m || vis[x][y] || grid[x][y] == '0' {
			return 
		}
		vis[x][y] = true
		grid[x][y] = 0
		dfs(x + 1, y)
		dfs(x - 1, y)
		dfs(x, y + 1)
		dfs(x, y - 1)
	}

	res := 0
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] == '1' {
				res++
				dfs(i, j)
			}
		}
	}

	return res
}